//给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。 
//
// 完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层
//为第 h 层，则该层包含 1~ 2ʰ 个节点。 
//
// 
//
// 示例 1： 
// 
// 
//输入：root = [1,2,3,4,5,6]
//输出：6
// 
//
// 示例 2： 
//
// 
//输入：root = []
//输出：0
// 
//
// 示例 3： 
//
// 
//输入：root = [1]
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 树中节点的数目范围是[0, 5 * 10⁴] 
// 0 <= Node.val <= 5 * 10⁴ 
// 题目数据保证输入的树是 完全二叉树 
// 
//
// 
//
// 进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？ 
//
// Related Topics 树 深度优先搜索 二分查找 二叉树 👍 963 👎 0


package leetcode.editor.cn;

// [222]完全二叉树的节点个数

public class CountCompleteTreeNodes_222 {
    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    private static TreeNode getTree() {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        return root;
    }

    public static void main(String[] args) {
        Solution solution = new CountCompleteTreeNodes_222().new Solution();
        System.out.println(solution.countNodes(getTree()));
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    class Solution {
        public int countNodes(TreeNode root) {
            if (root == null) {
                return 0;
            }
            TreeNode cur = root;
            int depthL = 1;
            int depthR = 1;
            int size = 0;
            while (cur.left != null) {
                cur = cur.left;
                depthL++;
            }
            cur = root;
            while (cur.right != null) {
                cur = cur.right;
                depthR++;
            }
            if (depthL == depthR) {
                return (int) (Math.pow(2, depthR) - 1);
            }
            size += (int) (Math.pow(2, depthR) - 1);
            int add = (int) Math.pow(2, depthR - 1);
            cur = root;
            //depth==2;
            while (--depthL > 0) {
                if (isHalf(cur, depthL)) {
                    size += add;
                    cur = cur.right;
                } else {
                    cur = cur.left;
                }
                add >>= 1;
            }
            return size;
        }

        private boolean isHalf(TreeNode root, int depth) {
            int step = 0;
            if (root.left != null) {
                root = root.left;
                step++;
            }
            while (root.right != null) {
                root = root.right;
                step++;
            }
            return step == depth;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}